// 文件名：deque_sliding_window.cpp
// 目的：在实时数据流中维护固定窗口的最大值，使用“单调队列”实现摊还 O(1) 的 push 与查询 max。
// 思路：
//   - samples_ 存储所有样本；mono_ 存储样本下标，维护一个“值单调不增”的双端队列：
//       - 入队：将队尾不大于当前值的下标逐个弹出，再把当前下标入队；
//       - 过期：窗口左边界之外的下标从队头弹出；
//   - 当前最大值即 mono_.front() 指向的样本值。
// 复杂度：
//   - pushSample：摊还 O(1)（每个元素最多进队出队各一次）；
//   - max：O(1)。
// 注意事项：
//   - 当没有样本时 max 返回 0.0（可按需改为 std::optional<double>）；
//   - windowSize_ 为窗口大小（样本个数），需 >= 1。

#include <deque>
#include <vector>
#include <iostream>

class SlidingMax {
public:
    explicit SlidingMax(std::size_t windowSize)
        : windowSize_(windowSize) {}

    // 推入一个样本，并维护单调队列与过期元素
    void pushSample(double value) {
        samples_.push_back(value);
        std::size_t idx = samples_.size() - 1;

        // 保持队列中值单调不增：移除所有不大于当前值的尾部下标
        while (!mono_.empty() && samples_[mono_.back()] <= value) {
            mono_.pop_back();
        }
        // 将当前下标入队
        mono_.push_back(idx);
        // 移除过期下标
        popExpired(idx);
    }

    // 查询当前窗口最大值
    double max() const {
        return mono_.empty() ? 0.0 : samples_[mono_.front()];
    }

private:
    // 移除窗口左边界之外的下标
    void popExpired(std::size_t currentIdx) {
        std::size_t minIdx = (currentIdx + 1 >= windowSize_)
                               ? currentIdx + 1 - windowSize_
                               : 0;
        while (!mono_.empty() && mono_.front() < minIdx) {
            mono_.pop_front();
        }
    }

    std::size_t windowSize_;
    std::vector<double> samples_;       // 原始样本序列
    std::deque<std::size_t> mono_;      // 单调队列（存索引，值单调不增）
};

int main() {
    SlidingMax window(3);
    for (double v : {1.2, 3.4, 2.1, 5.6, 4.0}) {
        window.pushSample(v);
        std::cout << "Current max: " << window.max() << '\n';
    }
    return 0;
}